What We're Building 🎯
- Структура данных: A очередь с приоритетом (ПО).
- Это абстрактный тип данных, подобный списку или очереди, но с одной особенностью.
- У каждого элемента есть «приоритет» (ключ).
- Когда вы выполняете операцию «pop», вы всегда получаете элемент с наибольшим приоритетом.всегда get the item with the highest priority.
- Операции:
- 1.
push(k) - 2.
peek() - 3.
pop()
- 1.
- Реализация: We'll use a бинарную макс-кучу.
- Почему куча? It's efficient! A heap gives us:
push: O(log N)pop: O(log N)peek: O(1)
What is a Max-Heap?
A binary tree with two simple rules:
1. Свойство формы
It's a полное бинарное дерево. Все уровни заполнены полностью, за исключением, возможно, последнего, который заполняется слева направо. Нет пропусков.
Нажмите на лист, чтобы удалить
2. Свойство макс-кучи
A parent's key is ключам детей. Это гарантирует, что самый большой элемент всегда находится в корне. its children's keys. This guarantees the наибольший element is always at the root.
Storing the Tree 💾
Because the tree is полным, его можно идеально хранить в простом массиве.
Index Math (0-based)
For a node at index i:
- Родитель
(i - 1) // 2 - Левый потомок
2 * i + 1 - Правый потомок
2 * i + 2
Совет: Memorize these formulas! They are the key to navigating the "tree" inside your array.